package offer;

/**
 * Creared with IntelliJ IDEA.
 * Description:请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 \begin{bmatrix} a & b & c &e \\ s & f & c & s \\ a & d & e& e\\ \end{bmatrix}\quad
 * ⎣
 * ⎡
 *
 * a
 * s
 * a
 *
 * b
 * f
 * d
 *
 * c
 * c
 * e
 *
 * e
 * s
 * e

 *   矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
 * User:yxd
 * Date:2022-07-18
 * Time:20:51
 */
import java.util.*;


public class JZ12 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */

    public boolean hasPath (char[][] matrix, String word) {
        //优先处理特殊情况
        if(matrix.length == 0)
            return false;
        int row = matrix.length;
        int col = matrix[0].length;
        //初始化flag矩阵记录是否走过
        boolean[][] flag = new boolean[row][col];
        //遍历矩阵找起点
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                //通过dfs找到路径
                if(DFS(matrix,flag,i,j,row,col,word,0))
                    return true;
            }
        }
        return false;

    }
    private boolean DFS(char[][] matrix,boolean[][] flag,int x,int y,int row,int col,String word,int k ){
        if(x < 0 || x >= row || y < 0 || y >= col || (matrix[x][y] != word.charAt(k)) || flag[x][y]){
            //超出范围或者当前位置的字符和要走的路径不一样，或者这条路已经走过了
            return false;
        }
        if(k == word.length() - 1) {
            //长度已经够了，就是满足条件的！
            return true;
        }
        //标记当前走过的位置
        flag[x][y] = true;
        //分别看四个方向的位置
        if(DFS(matrix,flag,x - 1,y,row,col,word,k + 1)
                || DFS(matrix,flag,x + 1,y,row,col,word,k + 1)
                || DFS(matrix,flag,x,y - 1,row,col,word,k + 1)
                || DFS(matrix,flag,x,y + 1,row,col,word,k + 1)){
            //任意一个方向满足条件就行
            return true;
        }
        //走到这里就需要进行回溯了
        flag[x][y] = false;
        return false;


    }
}